﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;
using System.Threading;
using System.Collections;
using System.Diagnostics;
using System.Reflection;
using Excel = Microsoft.Office.Interop.Excel;


namespace TSP
{
    public class DescFitness : IComparer
    {        
        int IComparer.Compare(Object x, Object y)
        {
            Chromosome c1 = (Chromosome)x;
            Chromosome c2 = (Chromosome)y;
            if (c1.Fitness > c2.Fitness)
            {
                return 1;
            }
            else
            {
                if(c1.Fitness < c2.Fitness)
                {
                    return -1;
                }
                else
                {
                    return 0;
                }
            }            
        }
    }
    public class Population
    {
        private static float _mutationRate = 0f;      
        private float _crossoverRate = 0f;
        private int _populationSize = 0;       
        private int _generationSize = 0;        
        private float _totalFitness = 0f;        
        private string _fileName = "";
        private string _excelFileName = "";      
        private int _seed = 0;
        private int _touranmentSize = 0;
        private int _percentLocalSearch = 0;
        private int _lengthLocalSearch = 0;
        private int _numEvaluate = 0;
        private float _maxCost = 0.0f;
                      
        private Random ran;
        private ArrayList presentPopulation;        
        private ArrayList nextPopulation;
        private bool _elitism = false;     
        private static Chromosome _bestChromosome = null;
              
        public delegate void WriteResulToFile(string fileName, int[] chr, float fitness, Stopwatch time);
        public WriteResulToFile writeResult;
        public delegate void WriteFitnessToFile(string fileName, ArrayList currentPop, float totalFitness, int repeatStt, Chromosome bestChromosome);
        public WriteFitnessToFile writeFitness;
            
        public ArrayList PresentPopulation
        {
            get { return presentPopulation; }
            set { presentPopulation = value; }
        }
        public int PopulationSize
        {
            get { return _populationSize; }
            set { _populationSize = value; }
        }             
        public string FileName
        {
            get { return _fileName; }
            set { _fileName = value; }
        }
        public string ExcelFileName
        {
            get { return _excelFileName; }
            set { _excelFileName = value; }
        }
        public int Seed
        {
            get { return _seed; }
            set { _seed = value; }
        }
        public bool Elitism
        {
            get { return _elitism; }
            set { _elitism = value; }
        }
        public static Chromosome BestChromosome
        {
            get { return Population._bestChromosome; }
            set { Population._bestChromosome = value; }
        }
        public static float MutationRate
        {
            get { return Population._mutationRate; }
            set { Population._mutationRate = value; }
        }
        public int TouranmentSize
        {
            get { return _touranmentSize; }
            set { _touranmentSize = value; }
        }
        public float MaxCost
        {
            get { return _maxCost; }
            set { _maxCost = value; }
        }

        //GA: giai_thuat(0); ten_file_du_lieu(1); so_lan_danh_gia(2); ti_le_lai_ghep(3); kich_thuoc_quan_the_ban_dau(4); tourament_size(5); elitis(6); seed(7);
        public Population(int numEvaluate, float crossoverRate, int populationSize, int touramentSize, bool elitism, int seed)
        {
            _mutationRate = (float)1 / (float)InOutData.NumOfCity;
            _crossoverRate = crossoverRate;
            _populationSize = populationSize;
            _generationSize = (int)((numEvaluate / populationSize));//(int)((numEvaluate / populationSize) * InOutData.NumOfCity);//100 * InOutData.NumOfCity;//50 * InOutData.NumOfCity;
            _touranmentSize = touramentSize;
            _seed = seed;
            _elitism = elitism;
            _numEvaluate = numEvaluate;
        }

        public Population(int numEvaluate, float crossoverRate, float mutationRate, int populationSize, int touramentSize, bool elitism, int seed, int percentLocalSearch, int lengthLocalSearch)
        {
            _mutationRate = mutationRate;
            _crossoverRate = crossoverRate;
            _populationSize = populationSize;
            _generationSize = (int)((numEvaluate*InOutData.NumOfCity)/(populationSize*(1 + percentLocalSearch/100.0)));//(int)(50*InOutData.NumOfCity/(1 + int.Parse(args[7])/100.0))
            _touranmentSize = touramentSize;
            _seed = seed;
            _elitism = elitism;
            _percentLocalSearch = percentLocalSearch;
            _lengthLocalSearch = lengthLocalSearch;
            _numEvaluate = numEvaluate; 
        }

        private void init()
        {
            presentPopulation = new ArrayList();        
            nextPopulation = new ArrayList();                          
            ran = new Random(_seed);       
        }

        public void createRandomPopulation()
        {
            presentPopulation.Clear();            
            for (int i = 0; i < _populationSize; i++)
            {
                Chromosome ch = new Chromosome(InOutData.NumOfCity);
                ch.createRandomChrome(ran);
                ch.calDistance = new Chromosome.CaculateDistance(InOutData.calculateDistance);
                ch.calculateFitness(_maxCost);                     
                presentPopulation.Add(ch);
            }           
        }    

        private float totalFitnessPopulation(ArrayList population)
        {
            float totalFitness = 0.0f;
            for (int i = 0; i < population.Count; i++)
            {
                Chromosome chro = (Chromosome)population[i];                           
                totalFitness += chro.Fitness;
            }
            return totalFitness;
        }              

        private int touranmentSelection(Random ran, ArrayList pop, int touramentSize)
        {
            int[] touranmetGroup = new int[touramentSize];
            int index = 0;
            int tempTour = 0;
            for (int i = 0; i < touramentSize; i++)
            {
                touranmetGroup[i] = ran.Next(_populationSize);
            }
            for (int i = 0; i < touramentSize - 1; i++)
            {
                index = i;
                for (int j = i + 1; j < touramentSize; j++)
                {
                    if (((Chromosome)pop[touranmetGroup[j]]).Fitness < ((Chromosome)pop[touranmetGroup[index]]).Fitness)
                    {
                        index = j;
                    }
                }
                if (index != i)
                {
                    tempTour = touranmetGroup[i];
                    touranmetGroup[i] = touranmetGroup[index];
                    touranmetGroup[index] = tempTour;
                }
            }
            return touranmetGroup[0];
        }

        private bool compareTour(Chromosome tour1, Chromosome tour2)
        {
            bool ok = true;
            for (int i = 0; i < InOutData.NumOfCity; i++)
            {
                if (tour1.chromo[i] != tour2.chromo[i])
                {
                    ok = false;
                    break;
                }
            }
            return ok;
        }

        //GA_MSCX
        public void createNextPopulationMSCX(ref ArrayList curPop, ArrayList nextPop, int touranmentSize)
        {
            int index = 0;
            int pidx1, pidx2;            
            Chromosome parent1 = new Chromosome(InOutData.NumOfCity);
            Chromosome parent2 = new Chromosome(InOutData.NumOfCity);
            Chromosome child1 = new Chromosome(InOutData.NumOfCity);
            Chromosome child2 = new Chromosome(InOutData.NumOfCity);
            nextPop.Clear();            
            for (int i = 0; i < _populationSize; i += 1)
            {
                pidx1 = touranmentSelection(ran, curPop, touranmentSize);
                pidx2  = touranmentSelection(ran, curPop, touranmentSize);                              
                parent1 = ((Chromosome)curPop[pidx1]);
                parent2 = ((Chromosome)curPop[pidx2]);
                if ((float)(ran.NextDouble()) < _crossoverRate)
                {
                    //parent1.modifiedOrderCrossover(parent2, out child1, out child2, ran);
                    parent1.modifiedSequentialContructiveCrossover(parent2, out child1, ran);
                    child1.inversionMutation(ran);
                    //child2.inversionMutation(ran);                                    
                    child1.calDistance = new Chromosome.CaculateDistance(InOutData.calculateDistance);
                    child1.calculateFitness(_maxCost);
                    nextPop.Add(child1);
                    //child2.calDistance = new Chromosome.CaculateDistance(InOutData.calculateDistance);
                    //child2.calculateFitness(_maxCost);
                    //nextPop.Add(child2);
                }
                else
                {
                    nextPop.Add(parent1);
                    //nextPop.Add(parent2);
                }                
            }
            curPop.Clear();                        
            for (int i = 0; i < _populationSize; i++)
            {
                curPop.Add((Chromosome)nextPop[i]);
                if (((Chromosome)nextPop[i]).Fitness < ((Chromosome)nextPop[index]).Fitness)
                {
                    index = i;
                }
            }          
            if (_elitism)
            {                    
                if (!compareTour(_bestChromosome,(Chromosome)curPop[index]))
                {                        
                    curPop.RemoveAt(0);
                    curPop.Add(_bestChromosome);                   
                }            
            }                                      
        }       
        public void GA_MSCX()
        {
            init();
            createRandomPopulation();
            _totalFitness = totalFitnessPopulation(presentPopulation);
            if (File.Exists(_fileName))
            {
                File.Delete(_fileName);
            }
            for (int i = 0; i < _generationSize; i++)
            {
                createNextPopulationMSCX(ref presentPopulation, nextPopulation, _touranmentSize);
                _totalFitness = totalFitnessPopulation(presentPopulation);
                writeFitness(_fileName, presentPopulation, _totalFitness, i + 1, _bestChromosome);
            }
        }

        //Select min of fitness of Parent 1, 2 and children
        public void createNextPopulationMSCX_1(ref ArrayList curPop, ArrayList nextPop, int touranmentSize)
        {
            int index = 0;
            int pidx1, pidx2;
            Chromosome parent1 = new Chromosome(InOutData.NumOfCity);
            Chromosome parent2 = new Chromosome(InOutData.NumOfCity);
            Chromosome child1 = new Chromosome(InOutData.NumOfCity);
            Chromosome child2 = new Chromosome(InOutData.NumOfCity);
            nextPop.Clear();
            for (int i = 0; i < _populationSize; i += 1)
            {
                pidx1 = touranmentSelection(ran, curPop, touranmentSize);
                pidx2 = touranmentSelection(ran, curPop, touranmentSize);
                parent1 = ((Chromosome)curPop[pidx1]);
                parent2 = ((Chromosome)curPop[pidx2]);
                if ((float)(ran.NextDouble()) < _crossoverRate)
                {
                    //parent1.modifiedOrderCrossover(parent2, out child1, out child2, ran);
                    parent1.modifiedSequentialContructiveCrossover(parent2, out child1, ran);
                    child1.inversionMutation(ran);
                    //child2.inversionMutation(ran);                                    
                    child1.calDistance = new Chromosome.CaculateDistance(InOutData.calculateDistance);
                    child1.calculateFitness(_maxCost);                   

                    if (child1.Fitness < parent1.Fitness)
                    {
                        if (child1.Fitness < parent2.Fitness)
                        {
                            nextPop.Add(child1);
                        }
                        else
                        {
                            nextPop.Add(parent2);
                        }
                    }
                    else
                    {
                        if (parent1.Fitness < parent2.Fitness)
                        {
                            nextPop.Add(parent1);
                        }
                        else
                        {
                            nextPop.Add(parent2);
                        }
                    }                   
                }
                else
                {
                    nextPop.Add(parent1);
                    //nextPop.Add(parent2);
                }
            }
            curPop.Clear();
            for (int i = 0; i < _populationSize; i++)
            {
                curPop.Add((Chromosome)nextPop[i]);
                if (((Chromosome)nextPop[i]).Fitness < ((Chromosome)nextPop[index]).Fitness)
                {
                    index = i;
                }
            }
            if (_elitism)
            {
                if (!compareTour(_bestChromosome, (Chromosome)curPop[index]))
                {
                    curPop.RemoveAt(0);
                    curPop.Add(_bestChromosome);
                }
            }
        }
        public void GA_MSCX_1()
        {
            init();
            createRandomPopulation();
            _totalFitness = totalFitnessPopulation(presentPopulation);
            if (File.Exists(_fileName))
            {
                File.Delete(_fileName);
            }
            for (int i = 0; i < _generationSize; i++)
            {
                createNextPopulationMSCX_1(ref presentPopulation, nextPopulation, _touranmentSize);
                _totalFitness = totalFitnessPopulation(presentPopulation);
                writeFitness(_fileName, presentPopulation, _totalFitness, i + 1, _bestChromosome);
            }
        }

        public void createNextPopulationMSCX_2(ref ArrayList curPop, ArrayList nextPop, int touranmentSize)
        {
            int index = 0;
            int pidx1, pidx2;
            Chromosome parent1 = new Chromosome(InOutData.NumOfCity);
            Chromosome parent2 = new Chromosome(InOutData.NumOfCity);
            Chromosome child1 = new Chromosome(InOutData.NumOfCity);
            Chromosome child2 = new Chromosome(InOutData.NumOfCity);
            nextPop.Clear();
            for (int i = 0; i < _populationSize; i += 1)
            {
                pidx1 = touranmentSelection(ran, curPop, touranmentSize);
                pidx2 = touranmentSelection(ran, curPop, touranmentSize);
                parent1 = ((Chromosome)curPop[pidx1]);
                parent2 = ((Chromosome)curPop[pidx2]);
                if ((float)(ran.NextDouble()) < _crossoverRate)
                {
                    //parent1.modifiedOrderCrossover(parent2, out child1, out child2, ran);
                    parent1.modifiedSequentialContructiveCrossover(parent2, out child1, ran);
                    child1.inversionMutation(ran);
                    //child2.inversionMutation(ran);                                    
                    child1.calDistance = new Chromosome.CaculateDistance(InOutData.calculateDistance);
                    child1.calculateFitness(_maxCost);

                    if (child1.Fitness < parent2.Fitness)
                    {
                        nextPop.Add(child1);
                    }
                    else
                    {
                        nextPop.Add(parent2);
                    }                    
                }
                else
                {
                    nextPop.Add(parent1);
                    //nextPop.Add(parent2);
                }
            }
            curPop.Clear();
            for (int i = 0; i < _populationSize; i++)
            {
                curPop.Add((Chromosome)nextPop[i]);
                if (((Chromosome)nextPop[i]).Fitness < ((Chromosome)nextPop[index]).Fitness)
                {
                    index = i;
                }
            }
            if (_elitism)
            {
                if (!compareTour(_bestChromosome, (Chromosome)curPop[index]))
                {
                    curPop.RemoveAt(0);
                    curPop.Add(_bestChromosome);
                }
            }
        }
        public void GA_MSCX_2()
        {
            init();
            createRandomPopulation();
            _totalFitness = totalFitnessPopulation(presentPopulation);
            if (File.Exists(_fileName))
            {
                File.Delete(_fileName);
            }
            for (int i = 0; i < _generationSize; i++)
            {
                createNextPopulationMSCX_2(ref presentPopulation, nextPopulation, _touranmentSize);
                _totalFitness = totalFitnessPopulation(presentPopulation);
                writeFitness(_fileName, presentPopulation, _totalFitness, i + 1, _bestChromosome);
            }
        }

        //GA_SCX
        public void createNextPopulationSCX(ref ArrayList curPop, ArrayList nextPop, int touranmentSize)
        {
            int index = 0;
            int pidx1, pidx2;
            Chromosome parent1 = new Chromosome(InOutData.NumOfCity);
            Chromosome parent2 = new Chromosome(InOutData.NumOfCity);
            Chromosome child1 = new Chromosome(InOutData.NumOfCity);
            Chromosome child2 = new Chromosome(InOutData.NumOfCity);
            nextPop.Clear();
            for (int i = 0; i < _populationSize; i += 1)
            {
                pidx1 = touranmentSelection(ran, curPop, touranmentSize);
                pidx2 = touranmentSelection(ran, curPop, touranmentSize);
                parent1 = ((Chromosome)curPop[pidx1]);
                parent2 = ((Chromosome)curPop[pidx2]);
                if ((float)(ran.NextDouble()) < _crossoverRate)
                {
                    //parent1.modifiedOrderCrossover(parent2, out child1, out child2, ran);
                    parent1.sequentialContructiveCrossover(parent2, out child1, ran);
                    child1.inversionMutation(ran);
                    //child2.inversionMutation(ran);                                    
                    child1.calDistance = new Chromosome.CaculateDistance(InOutData.calculateDistance);
                    child1.calculateFitness(_maxCost);
                    nextPop.Add(child1);
                    //child2.calDistance = new Chromosome.CaculateDistance(InOutData.calculateDistance);
                    //child2.calculateFitness(_maxCost);
                    //nextPop.Add(child2);
                }
                else
                {
                    nextPop.Add(parent1);
                    //nextPop.Add(parent2);
                }
            }
            curPop.Clear();
            for (int i = 0; i < _populationSize; i++)
            {
                curPop.Add((Chromosome)nextPop[i]);
                if (((Chromosome)nextPop[i]).Fitness < ((Chromosome)nextPop[index]).Fitness)
                {
                    index = i;
                }
            }
            if (_elitism)
            {
                if (!compareTour(_bestChromosome, (Chromosome)curPop[index]))
                {
                    curPop.RemoveAt(0);
                    curPop.Add(_bestChromosome);
                }
            }
        }
        public void GA_SCX()
        {
            init();
            createRandomPopulation();
            _totalFitness = totalFitnessPopulation(presentPopulation);
            if (File.Exists(_fileName))
            {
                File.Delete(_fileName);
            }
            for (int i = 0; i < _generationSize; i++)
            {
                createNextPopulationSCX(ref presentPopulation, nextPopulation, _touranmentSize);
                _totalFitness = totalFitnessPopulation(presentPopulation);
                writeFitness(_fileName, presentPopulation, _totalFitness, i + 1, _bestChromosome);
            }
        }

        //GA_OX
        public void createNextPopulationOX(ref ArrayList curPop, ArrayList nextPop, int touranmentSize)
        {
            int index = 0;
            int pidx1, pidx2;
            Chromosome parent1 = new Chromosome(InOutData.NumOfCity);
            Chromosome parent2 = new Chromosome(InOutData.NumOfCity);
            Chromosome child1 = new Chromosome(InOutData.NumOfCity);
            Chromosome child2 = new Chromosome(InOutData.NumOfCity);
            nextPop.Clear();
            for (int i = 0; i < _populationSize; i += 2)
            {
                pidx1 = touranmentSelection(ran, curPop, touranmentSize);
                pidx2 = touranmentSelection(ran, curPop, touranmentSize);
                parent1 = ((Chromosome)curPop[pidx1]);
                parent2 = ((Chromosome)curPop[pidx2]);
                if ((float)(ran.NextDouble()) < _crossoverRate)
                {
                    parent1.orderCrossover(parent2, out child1, out child2, ran);
                    child1.inversionMutation(ran);
                    child2.inversionMutation(ran);                                    
                    child1.calDistance = new Chromosome.CaculateDistance(InOutData.calculateDistance);
                    child1.calculateFitness(_maxCost);
                    nextPop.Add(child1);
                    child2.calDistance = new Chromosome.CaculateDistance(InOutData.calculateDistance);
                    child2.calculateFitness(_maxCost);
                    nextPop.Add(child2);
                }
                else
                {
                    nextPop.Add(parent1);
                    nextPop.Add(parent2);
                }
            }
            curPop.Clear();
            for (int i = 0; i < _populationSize; i++)
            {
                curPop.Add((Chromosome)nextPop[i]);
                if (((Chromosome)nextPop[i]).Fitness < ((Chromosome)nextPop[index]).Fitness)
                {
                    index = i;
                }
            }
            if (_elitism)
            {
                if (!compareTour(_bestChromosome, (Chromosome)curPop[index]))
                {
                    curPop.RemoveAt(0);
                    curPop.Add(_bestChromosome);
                }
            }
        }
        public void GA_OX()
        {
            init();
            createRandomPopulation();
            _totalFitness = totalFitnessPopulation(presentPopulation);
            if (File.Exists(_fileName))
            {
                File.Delete(_fileName);
            }
            for (int i = 0; i < _generationSize; i++)
            {
                createNextPopulationOX(ref presentPopulation, nextPopulation, _touranmentSize);
                _totalFitness = totalFitnessPopulation(presentPopulation);
                writeFitness(_fileName, presentPopulation, _totalFitness, i + 1, _bestChromosome);
            }
        }

        //GA_MOX
        public void createNextPopulationMOX(ref ArrayList curPop, ArrayList nextPop, int touranmentSize)
        {
            int index = 0;
            int pidx1, pidx2;
            Chromosome parent1 = new Chromosome(InOutData.NumOfCity);
            Chromosome parent2 = new Chromosome(InOutData.NumOfCity);
            Chromosome child1 = new Chromosome(InOutData.NumOfCity);
            Chromosome child2 = new Chromosome(InOutData.NumOfCity);
            nextPop.Clear();
            for (int i = 0; i < _populationSize; i += 2)
            {
                pidx1 = touranmentSelection(ran, curPop, touranmentSize);
                pidx2 = touranmentSelection(ran, curPop, touranmentSize);
                parent1 = ((Chromosome)curPop[pidx1]);
                parent2 = ((Chromosome)curPop[pidx2]);
                if ((float)(ran.NextDouble()) < _crossoverRate)
                {
                    parent1.modifiedOrderCrossover(parent2, out child1, out child2, ran);
                    child1.inversionMutation(ran);
                    child2.inversionMutation(ran);
                    child1.calDistance = new Chromosome.CaculateDistance(InOutData.calculateDistance);
                    child1.calculateFitness(_maxCost);
                    nextPop.Add(child1);
                    child2.calDistance = new Chromosome.CaculateDistance(InOutData.calculateDistance);
                    child2.calculateFitness(_maxCost);
                    nextPop.Add(child2);
                }
                else
                {
                    nextPop.Add(parent1);
                    nextPop.Add(parent2);
                }
            }
            curPop.Clear();
            for (int i = 0; i < _populationSize; i++)
            {
                curPop.Add((Chromosome)nextPop[i]);
                if (((Chromosome)nextPop[i]).Fitness < ((Chromosome)nextPop[index]).Fitness)
                {
                    index = i;
                }
            }
            if (_elitism)
            {
                if (!compareTour(_bestChromosome, (Chromosome)curPop[index]))
                {
                    curPop.RemoveAt(0);
                    curPop.Add(_bestChromosome);
                }
            }
        }
        public void GA_MOX()
        {
            init();
            createRandomPopulation();
            _totalFitness = totalFitnessPopulation(presentPopulation);
            if (File.Exists(_fileName))
            {
                File.Delete(_fileName);
            }
            for (int i = 0; i < _generationSize; i++)
            {
                createNextPopulationMOX(ref presentPopulation, nextPopulation, _touranmentSize);
                _totalFitness = totalFitnessPopulation(presentPopulation);
                writeFitness(_fileName, presentPopulation, _totalFitness, i + 1, _bestChromosome);
            }
        }

        //Modify MSCX: search all element
        public void createNextPopulation_M_MSCX(ref ArrayList curPop, ArrayList nextPop, int touranmentSize)
        {
            int index = 0;
            int pidx1, pidx2;
            Chromosome parent1 = new Chromosome(InOutData.NumOfCity);
            Chromosome parent2 = new Chromosome(InOutData.NumOfCity);
            Chromosome child1 = new Chromosome(InOutData.NumOfCity);
            Chromosome child2 = new Chromosome(InOutData.NumOfCity);
            nextPop.Clear();
            for (int i = 0; i < _populationSize; i += 1)
            {
                pidx1 = touranmentSelection(ran, curPop, touranmentSize);
                pidx2 = touranmentSelection(ran, curPop, touranmentSize);
                parent1 = ((Chromosome)curPop[pidx1]);
                parent2 = ((Chromosome)curPop[pidx2]);
                if ((float)(ran.NextDouble()) < _crossoverRate)
                {
                    parent1.M_MSCX(parent2, out child1, ran);
                    child1.inversionMutation(ran);                              
                    child1.calDistance = new Chromosome.CaculateDistance(InOutData.calculateDistance);
                    child1.calculateFitness(_maxCost);
                    nextPop.Add(child1);
                }
                else
                {
                    nextPop.Add(parent1);
                }
            }
            curPop.Clear();
            for (int i = 0; i < _populationSize; i++)
            {
                curPop.Add((Chromosome)nextPop[i]);
                if (((Chromosome)nextPop[i]).Fitness < ((Chromosome)nextPop[index]).Fitness)
                {
                    index = i;
                }
            }
            if (_elitism)
            {
                if (!compareTour(_bestChromosome, (Chromosome)curPop[index]))
                {
                    curPop.RemoveAt(0);
                    curPop.Add(_bestChromosome);
                }
            }
        }
        public void GA_M_MSCX()
        {
            init();
            createRandomPopulation();
            _totalFitness = totalFitnessPopulation(presentPopulation);
            if (File.Exists(_fileName))
            {
                File.Delete(_fileName);
            }
            for (int i = 0; i < _generationSize; i++)
            {
                createNextPopulation_M_MSCX(ref presentPopulation, nextPopulation, _touranmentSize);
                _totalFitness = totalFitnessPopulation(presentPopulation);
                writeFitness(_fileName, presentPopulation, _totalFitness, i + 1, _bestChromosome);
            }
        }


        //Modify MSCX: search before and after current city
        public void createNextPopulation_M_MSCX1(ref ArrayList curPop, ArrayList nextPop, int touranmentSize)
        {
            int index = 0;
            int pidx1, pidx2;
            Chromosome parent1 = new Chromosome(InOutData.NumOfCity);
            Chromosome parent2 = new Chromosome(InOutData.NumOfCity);
            Chromosome child1 = new Chromosome(InOutData.NumOfCity);
            Chromosome child2 = new Chromosome(InOutData.NumOfCity);
            nextPop.Clear();
            for (int i = 0; i < _populationSize; i += 1)
            {
                pidx1 = touranmentSelection(ran, curPop, touranmentSize);
                pidx2 = touranmentSelection(ran, curPop, touranmentSize);
                parent1 = ((Chromosome)curPop[pidx1]);
                parent2 = ((Chromosome)curPop[pidx2]);
                if ((float)(ran.NextDouble()) < _crossoverRate)
                {
                    parent1.M_MSCX1(parent2, out child1, ran);
                    child1.inversionMutation(ran);
                    child1.calDistance = new Chromosome.CaculateDistance(InOutData.calculateDistance);
                    child1.calculateFitness(_maxCost);
                    nextPop.Add(child1);
                }
                else
                {
                    nextPop.Add(parent1);
                }
            }
            curPop.Clear();
            for (int i = 0; i < _populationSize; i++)
            {
                curPop.Add((Chromosome)nextPop[i]);
                if (((Chromosome)nextPop[i]).Fitness < ((Chromosome)nextPop[index]).Fitness)
                {
                    index = i;
                }
            }
            if (_elitism)
            {
                if (!compareTour(_bestChromosome, (Chromosome)curPop[index]))
                {
                    curPop.RemoveAt(0);
                    curPop.Add(_bestChromosome);
                }
            }
        }
        public void GA_M_MSCX1()
        {
            init();
            createRandomPopulation();
            _totalFitness = totalFitnessPopulation(presentPopulation);
            if (File.Exists(_fileName))
            {
                File.Delete(_fileName);
            }
            for (int i = 0; i < _generationSize; i++)
            {
                createNextPopulation_M_MSCX1(ref presentPopulation, nextPopulation, _touranmentSize);
                _totalFitness = totalFitnessPopulation(presentPopulation);
                writeFitness(_fileName, presentPopulation, _totalFitness, i + 1, _bestChromosome);
            }
        }

        public void createNextPopulation_M_MSCX1_1(ref ArrayList curPop, ArrayList nextPop, int touranmentSize)
        {
            int index = 0;
            int pidx1, pidx2;
            Chromosome parent1 = new Chromosome(InOutData.NumOfCity);
            Chromosome parent2 = new Chromosome(InOutData.NumOfCity);
            Chromosome child1 = new Chromosome(InOutData.NumOfCity);
            Chromosome child2 = new Chromosome(InOutData.NumOfCity);
            nextPop.Clear();
            for (int i = 0; i < _populationSize; i += 1)
            {
                pidx1 = touranmentSelection(ran, curPop, touranmentSize);
                pidx2 = touranmentSelection(ran, curPop, touranmentSize);
                parent1 = ((Chromosome)curPop[pidx1]);
                parent2 = ((Chromosome)curPop[pidx2]);
                if ((float)(ran.NextDouble()) < _crossoverRate)
                {
                    parent1.M_MSCX1_1(parent2, out child1, ran);
                    child1.inversionMutation(ran);
                    child1.calDistance = new Chromosome.CaculateDistance(InOutData.calculateDistance);
                    child1.calculateFitness(_maxCost);
                    nextPop.Add(child1);
                }
                else
                {
                    nextPop.Add(parent1);
                }
            }
            curPop.Clear();
            for (int i = 0; i < _populationSize; i++)
            {
                curPop.Add((Chromosome)nextPop[i]);
                if (((Chromosome)nextPop[i]).Fitness < ((Chromosome)nextPop[index]).Fitness)
                {
                    index = i;
                }
            }
            if (_elitism)
            {
                if (!compareTour(_bestChromosome, (Chromosome)curPop[index]))
                {
                    curPop.RemoveAt(0);
                    curPop.Add(_bestChromosome);
                }
            }
        }
        public void GA_M_MSCX1_1()
        {
            init();
            createRandomPopulation();
            _totalFitness = totalFitnessPopulation(presentPopulation);
            if (File.Exists(_fileName))
            {
                File.Delete(_fileName);
            }
            for (int i = 0; i < _generationSize; i++)
            {
                createNextPopulation_M_MSCX1_1(ref presentPopulation, nextPopulation, _touranmentSize);
                _totalFitness = totalFitnessPopulation(presentPopulation);
                writeFitness(_fileName, presentPopulation, _totalFitness, i + 1, _bestChromosome);
            }
        }

        //Modify MSCX: search before and after current city, keep commont edge
        public void createNextPopulation_M_MSCX2(ref ArrayList curPop, ArrayList nextPop, int touranmentSize)
        {
            int index = 0;
            int pidx1, pidx2;
            Chromosome parent1 = new Chromosome(InOutData.NumOfCity);
            Chromosome parent2 = new Chromosome(InOutData.NumOfCity);
            Chromosome child1 = new Chromosome(InOutData.NumOfCity);
            Chromosome child2 = new Chromosome(InOutData.NumOfCity);
            nextPop.Clear();
            for (int i = 0; i < _populationSize; i += 1)
            {
                pidx1 = touranmentSelection(ran, curPop, touranmentSize);
                pidx2 = touranmentSelection(ran, curPop, touranmentSize);
                parent1 = ((Chromosome)curPop[pidx1]);
                parent2 = ((Chromosome)curPop[pidx2]);
                if ((float)(ran.NextDouble()) < _crossoverRate)
                {
                    parent1.M_MSCX2(parent2, out child1, ran);
                    child1.inversionMutation(ran);
                    child1.calDistance = new Chromosome.CaculateDistance(InOutData.calculateDistance);
                    child1.calculateFitness(_maxCost);
                    nextPop.Add(child1);
                }
                else
                {
                    nextPop.Add(parent1);
                }
            }
            curPop.Clear();
            for (int i = 0; i < _populationSize; i++)
            {
                curPop.Add((Chromosome)nextPop[i]);
                if (((Chromosome)nextPop[i]).Fitness < ((Chromosome)nextPop[index]).Fitness)
                {
                    index = i;
                }
            }
            if (_elitism)
            {
                if (!compareTour(_bestChromosome, (Chromosome)curPop[index]))
                {
                    curPop.RemoveAt(0);
                    curPop.Add(_bestChromosome);
                }
            }
        }
        public void GA_M_MSCX2()
        {
            init();
            createRandomPopulation();
            _totalFitness = totalFitnessPopulation(presentPopulation);
            if (File.Exists(_fileName))
            {
                File.Delete(_fileName);
            }
            for (int i = 0; i < _generationSize; i++)
            {
                createNextPopulation_M_MSCX2(ref presentPopulation, nextPopulation, _touranmentSize);
                _totalFitness = totalFitnessPopulation(presentPopulation);
                writeFitness(_fileName, presentPopulation, _totalFitness, i + 1, _bestChromosome);
            }
        }

        //Modify MSCX: search in list of current city
        public void createNextPopulation_M_MSCX3(ref ArrayList curPop, ArrayList nextPop, int touranmentSize, List<int>[] lstCity)
        {
            int index = 0;
            int pidx1, pidx2;
            Chromosome parent1 = new Chromosome(InOutData.NumOfCity);
            Chromosome parent2 = new Chromosome(InOutData.NumOfCity);
            Chromosome child1 = new Chromosome(InOutData.NumOfCity);
            Chromosome child2 = new Chromosome(InOutData.NumOfCity);
            nextPop.Clear();
            for (int i = 0; i < _populationSize; i += 1)
            {
                pidx1 = touranmentSelection(ran, curPop, touranmentSize);
                pidx2 = touranmentSelection(ran, curPop, touranmentSize);
                parent1 = ((Chromosome)curPop[pidx1]);
                parent2 = ((Chromosome)curPop[pidx2]);
                if ((float)(ran.NextDouble()) < _crossoverRate)
                {
                    parent1.M_MSCX3(parent2, out child1, ran, lstCity);
                    child1.inversionMutation(ran);
                    child1.calDistance = new Chromosome.CaculateDistance(InOutData.calculateDistance);
                    child1.calculateFitness(_maxCost);
                    nextPop.Add(child1);
                }
                else
                {
                    nextPop.Add(parent1);
                }
            }
            curPop.Clear();
            for (int i = 0; i < _populationSize; i++)
            {
                curPop.Add((Chromosome)nextPop[i]);
                if (((Chromosome)nextPop[i]).Fitness < ((Chromosome)nextPop[index]).Fitness)
                {
                    index = i;
                }
            }
            if (_elitism)
            {
                if (!compareTour(_bestChromosome, (Chromosome)curPop[index]))
                {
                    curPop.RemoveAt(0);
                    curPop.Add(_bestChromosome);
                }
            }
        }

        public void GA_M_MSCX3()
        {
            init();
            createRandomPopulation();
            _totalFitness = totalFitnessPopulation(presentPopulation);
            if (File.Exists(_fileName))
            {
                File.Delete(_fileName);
            }

            List<int>[] lstCity = new List<int>[InOutData.NumOfCity];
            for (int i = 0; i < InOutData.NumOfCity; i++)
            {
                lstCity[i] = new List<int>();
            }

            for (int i = 0; i < _generationSize; i++)
            {
                createNextPopulation_M_MSCX3(ref presentPopulation, nextPopulation, _touranmentSize, lstCity);
                _totalFitness = totalFitnessPopulation(presentPopulation);
                writeFitness(_fileName, presentPopulation, _totalFitness, i + 1, _bestChromosome);
            }
        }

        //Modify MSCX: search use best city
        public void createNextPopulation_M_MSCX4(ref ArrayList curPop, ArrayList nextPop, int touranmentSize, int[] toCity, float[] bestDistance)
        {
            int index = 0;
            int pidx1, pidx2;
            Chromosome parent1 = new Chromosome(InOutData.NumOfCity);
            Chromosome parent2 = new Chromosome(InOutData.NumOfCity);
            Chromosome child1 = new Chromosome(InOutData.NumOfCity);
            Chromosome child2 = new Chromosome(InOutData.NumOfCity);
            nextPop.Clear();
            for (int i = 0; i < _populationSize; i += 1)
            {
                pidx1 = touranmentSelection(ran, curPop, touranmentSize);
                pidx2 = touranmentSelection(ran, curPop, touranmentSize);
                parent1 = ((Chromosome)curPop[pidx1]);
                parent2 = ((Chromosome)curPop[pidx2]);
                if ((float)(ran.NextDouble()) < _crossoverRate)
                {
                    parent1.M_MSCX4(parent2, out child1, ran, toCity, bestDistance);
                    child1.inversionMutation(ran);
                    child1.calDistance = new Chromosome.CaculateDistance(InOutData.calculateDistance);
                    child1.calculateFitness(_maxCost);
                    nextPop.Add(child1);
                }
                else
                {
                    nextPop.Add(parent1);
                }
            }
            curPop.Clear();
            for (int i = 0; i < _populationSize; i++)
            {
                curPop.Add((Chromosome)nextPop[i]);
                if (((Chromosome)nextPop[i]).Fitness < ((Chromosome)nextPop[index]).Fitness)
                {
                    index = i;
                }
            }
            if (_elitism)
            {
                if (!compareTour(_bestChromosome, (Chromosome)curPop[index]))
                {
                    curPop.RemoveAt(0);
                    curPop.Add(_bestChromosome);
                }
            }
        }

        public void GA_M_MSCX4()
        {
            init();
            createRandomPopulation();
            _totalFitness = totalFitnessPopulation(presentPopulation);
            if (File.Exists(_fileName))
            {
                File.Delete(_fileName);
            }

          

            int[] toCity = new int[InOutData.NumOfCity];
            for (int i = 0; i < InOutData.NumOfCity; i++)
            {
                toCity[i] = -1;
            }
            float[] bestDistance = new float[InOutData.NumOfCity];
            for (int i = 0; i < InOutData.NumOfCity; i++)
            {
                bestDistance[i] = float.MaxValue;
            }

            for (int i = 0; i < _generationSize; i++)
            {
                createNextPopulation_M_MSCX4(ref presentPopulation, nextPopulation, _touranmentSize, toCity, bestDistance);
                _totalFitness = totalFitnessPopulation(presentPopulation);
                writeFitness(_fileName, presentPopulation, _totalFitness, i + 1, _bestChromosome);
            }
        }


        //Modify MSCX: search use best city
        public void createNextPopulation_M_MSCX5(ref ArrayList curPop, ArrayList nextPop, int touranmentSize, int[] toCity, float[] bestDistance)
        {
            int index = 0;
            int pidx1, pidx2;
            Chromosome parent1 = new Chromosome(InOutData.NumOfCity);
            Chromosome parent2 = new Chromosome(InOutData.NumOfCity);
            Chromosome child1 = new Chromosome(InOutData.NumOfCity);
            Chromosome child2 = new Chromosome(InOutData.NumOfCity);
            nextPop.Clear();
            for (int i = 0; i < _populationSize; i += 1)
            {
                pidx1 = touranmentSelection(ran, curPop, touranmentSize);
                pidx2 = touranmentSelection(ran, curPop, touranmentSize);
                parent1 = ((Chromosome)curPop[pidx1]);
                parent2 = ((Chromosome)curPop[pidx2]);
                if ((float)(ran.NextDouble()) < _crossoverRate)
                {
                    parent1.M_MSCX5(parent2, out child1, ran, toCity, bestDistance);
                    child1.inversionMutation(ran);
                    child1.calDistance = new Chromosome.CaculateDistance(InOutData.calculateDistance);
                    child1.calculateFitness(_maxCost);
                    nextPop.Add(child1);
                }
                else
                {
                    nextPop.Add(parent1);
                }
            }
            curPop.Clear();
            for (int i = 0; i < _populationSize; i++)
            {
                curPop.Add((Chromosome)nextPop[i]);
                if (((Chromosome)nextPop[i]).Fitness < ((Chromosome)nextPop[index]).Fitness)
                {
                    index = i;
                }
            }
            if (_elitism)
            {
                if (!compareTour(_bestChromosome, (Chromosome)curPop[index]))
                {
                    curPop.RemoveAt(0);
                    curPop.Add(_bestChromosome);
                }
            }
        }

        public void GA_M_MSCX5()
        {
            init();
            createRandomPopulation();
            _totalFitness = totalFitnessPopulation(presentPopulation);
            if (File.Exists(_fileName))
            {
                File.Delete(_fileName);
            }



            int[] toCity = new int[InOutData.NumOfCity];
            for (int i = 0; i < InOutData.NumOfCity; i++)
            {
                toCity[i] = -1;
            }
            float[] bestDistance = new float[InOutData.NumOfCity];
            for (int i = 0; i < InOutData.NumOfCity; i++)
            {
                bestDistance[i] = float.MaxValue;
            }

            for (int i = 0; i < _generationSize; i++)
            {
                createNextPopulation_M_MSCX5(ref presentPopulation, nextPopulation, _touranmentSize, toCity, bestDistance);
                _totalFitness = totalFitnessPopulation(presentPopulation);
                writeFitness(_fileName, presentPopulation, _totalFitness, i + 1, _bestChromosome);
            }
        }


        //Crossover using 3 parents
        public void createNextPopulation_M_MSCX6(ref ArrayList curPop, ArrayList nextPop, int touranmentSize, int[] toCity, float[] bestDistance)
        {
            int index = 0;
            int pidx1, pidx2, pidx3;
            Chromosome parent1 = new Chromosome(InOutData.NumOfCity);
            Chromosome parent2 = new Chromosome(InOutData.NumOfCity);
            Chromosome parent3 = new Chromosome(InOutData.NumOfCity);

            Chromosome child1 = new Chromosome(InOutData.NumOfCity);
          
            nextPop.Clear();
            for (int i = 0; i < _populationSize; i += 1)
            {
                pidx1 = touranmentSelection(ran, curPop, touranmentSize);
                pidx2 = touranmentSelection(ran, curPop, touranmentSize);
                pidx3 = touranmentSelection(ran, curPop, touranmentSize);

                parent1 = ((Chromosome)curPop[pidx1]);
                parent2 = ((Chromosome)curPop[pidx2]);
                parent3 = ((Chromosome)curPop[pidx3]);

                if ((float)(ran.NextDouble()) < _crossoverRate)
                {
                    parent1.M_MSCX6_1(parent2, parent3, out child1, ran);
                    child1.inversionMutation(ran);
                    child1.calDistance = new Chromosome.CaculateDistance(InOutData.calculateDistance);
                    child1.calculateFitness(_maxCost);
                    nextPop.Add(child1);
                }
                else
                {
                    nextPop.Add(parent1);
                }
            }
            curPop.Clear();
            for (int i = 0; i < _populationSize; i++)
            {
                curPop.Add((Chromosome)nextPop[i]);
                if (((Chromosome)nextPop[i]).Fitness < ((Chromosome)nextPop[index]).Fitness)
                {
                    index = i;
                }
            }
            if (_elitism)
            {
                if (!compareTour(_bestChromosome, (Chromosome)curPop[index]))
                {
                    curPop.RemoveAt(0);
                    curPop.Add(_bestChromosome);
                }
            }
        }

        public void GA_M_MSCX6()
        {
            init();
            createRandomPopulation();
            _totalFitness = totalFitnessPopulation(presentPopulation);
            if (File.Exists(_fileName))
            {
                File.Delete(_fileName);
            }



            int[] toCity = new int[InOutData.NumOfCity];
            for (int i = 0; i < InOutData.NumOfCity; i++)
            {
                toCity[i] = -1;
            }
            float[] bestDistance = new float[InOutData.NumOfCity];
            for (int i = 0; i < InOutData.NumOfCity; i++)
            {
                bestDistance[i] = float.MaxValue;
            }

            for (int i = 0; i < _generationSize; i++)
            {
                createNextPopulation_M_MSCX6(ref presentPopulation, nextPopulation, _touranmentSize, toCity, bestDistance);
                _totalFitness = totalFitnessPopulation(presentPopulation);
                writeFitness(_fileName, presentPopulation, _totalFitness, i + 1, _bestChromosome);
            }
        }

        //Crossover using simple closed path
        private double theta(Point p1, Point p2)
        {
            int dx, dy, ax, ay;
            double t;
            dx = p2.X - p1.X;
            ax = Math.Abs(dx);
            dy = p2.Y - p1.Y;
            ay = Math.Abs(dy);

            if ((dx == 0) && (dy == 0))
            {
                t = 0.0;
            }
            else
            {
                t = dy / (ax + ay);
            }

            if (dx < 0)
            {
                t = 2 - t;
            }
            else
            {
                if (dy < 0)
                {
                    t = 4 + t;
                }
            }
            return t * 90.0;
        }

        private int[] sortCities(Point[] cities, int numCt)
        {
            int[] index = new int[numCt];
            double[] angle = new double[numCt];
            int temp;
            for (int i = 0; i < numCt; i++)
            {
                index[i] = i;
                angle[i] = theta(cities[0], cities[i]);
            }
            for (int i = 0; i < numCt - 1; i++)
                for (int j = i + 1; j < numCt; j++)
                {
                    if (angle[index[i]] > angle[index[j]])
                    {
                        temp = index[i];
                        index[i] = index[j];
                        index[j] = temp;
                    }
                }
            return index;
        }

        public void createNextPopulation_M_MSCX7(ref ArrayList curPop, ArrayList nextPop, int touranmentSize, int[] indexArr)
        {
            int index = 0;
            int pidx1, pidx2;
            Chromosome parent1 = new Chromosome(InOutData.NumOfCity);
            Chromosome parent2 = new Chromosome(InOutData.NumOfCity);
          
            Chromosome child1 = new Chromosome(InOutData.NumOfCity);

            nextPop.Clear();

            for (int i = 0; i < _populationSize; i += 1)
            {
                pidx1 = touranmentSelection(ran, curPop, touranmentSize);
                pidx2 = touranmentSelection(ran, curPop, touranmentSize);
            
                parent1 = ((Chromosome)curPop[pidx1]);
                parent2 = ((Chromosome)curPop[pidx2]);
              
                if ((float)(ran.NextDouble()) < _crossoverRate)
                {
                    parent1.M_MSCX7_2(parent2, out child1, indexArr, ran);
                    child1.inversionMutation(ran);
                    child1.calDistance = new Chromosome.CaculateDistance(InOutData.calculateDistance);
                    child1.calculateFitness(_maxCost);
                    nextPop.Add(child1);
                }
                else
                {
                    nextPop.Add(parent1);
                }
            }
            curPop.Clear();

            for (int i = 0; i < _populationSize; i++)
            {
                curPop.Add((Chromosome)nextPop[i]);
                if (((Chromosome)nextPop[i]).Fitness < ((Chromosome)nextPop[index]).Fitness)
                {
                    index = i;
                }
            }
            if (_elitism)
            {
                if (!compareTour(_bestChromosome, (Chromosome)curPop[index]))
                {
                    curPop.RemoveAt(0);
                    curPop.Add(_bestChromosome);
                }
            }
        }

        public void GA_M_MSCX7()
        {
            init();
            createRandomPopulation();
            _totalFitness = totalFitnessPopulation(presentPopulation);
            if (File.Exists(_fileName))
            {
                File.Delete(_fileName);
            }

            int[] indexArr = new int[InOutData.NumOfCity];
            indexArr = sortCities(InOutData.cities, InOutData.NumOfCity);

            for (int i = 0; i < _generationSize; i++)
            {
                createNextPopulation_M_MSCX7(ref presentPopulation, nextPopulation, _touranmentSize, indexArr);
                _totalFitness = totalFitnessPopulation(presentPopulation);
                writeFitness(_fileName, presentPopulation, _totalFitness, i + 1, _bestChromosome);
            }
        }


        //GA use linear distance       
        public void createNextPopulation_LinearDistance(ref ArrayList curPop, ArrayList nextPop, int touranmentSize)
        {
            int index = 0;
            int pidx1, pidx2;            
            Chromosome parent1 = new Chromosome(InOutData.NumOfCity);
            Chromosome parent2 = new Chromosome(InOutData.NumOfCity);
            Chromosome child1 = new Chromosome(InOutData.NumOfCity);
            Chromosome child2 = new Chromosome(InOutData.NumOfCity);
            nextPop.Clear();            
            for (int i = 0; i < _populationSize; i += 1)
            {
                pidx1 = touranmentSelection(ran, curPop, touranmentSize);
                pidx2  = touranmentSelection(ran, curPop, touranmentSize);                              
                parent1 = ((Chromosome)curPop[pidx1]);
                parent2 = ((Chromosome)curPop[pidx2]);
                if ((float)(ran.NextDouble()) < _crossoverRate)
                {                    
                    parent1.linearDistanceCrossover(parent2, out child1, ran);
                    child1.inversionMutation(ran);                                            
                    child1.calDistance = new Chromosome.CaculateDistance(InOutData.calculateDistance);
                    child1.calculateFitness(_maxCost);
                    nextPop.Add(child1);                  
                }
                else
                {
                    nextPop.Add(parent1);                    
                }                
            }
            curPop.Clear();                        
            for (int i = 0; i < _populationSize; i++)
            {
                curPop.Add((Chromosome)nextPop[i]);
                if (((Chromosome)nextPop[i]).Fitness < ((Chromosome)nextPop[index]).Fitness)
                {
                    index = i;
                }
            }          
            if (_elitism)
            {                    
                if (!compareTour(_bestChromosome,(Chromosome)curPop[index]))
                {                        
                    curPop.RemoveAt(0);
                    curPop.Add(_bestChromosome);                   
                }            
            }                                      
        }       
        public void GA_LinearDistance()
        {
            init();
            createRandomPopulation();
            _totalFitness = totalFitnessPopulation(presentPopulation);
            if (File.Exists(_fileName))
            {
                File.Delete(_fileName);
            }
            for (int i = 0; i < _generationSize; i++)
            {
                createNextPopulation_LinearDistance(ref presentPopulation, nextPopulation, _touranmentSize);
                _totalFitness = totalFitnessPopulation(presentPopulation);
                writeFitness(_fileName, presentPopulation, _totalFitness, i + 1, _bestChromosome);
            }
        }

        //GA use linear distance 1      
        public void createNextPopulation_LinearDistance1(ref ArrayList curPop, ArrayList nextPop, int touranmentSize, float alpha1, float alpha2, float beta)
        {
            int index = 0;
            int pidx1, pidx2;
            Chromosome parent1 = new Chromosome(InOutData.NumOfCity);
            Chromosome parent2 = new Chromosome(InOutData.NumOfCity);
            Chromosome child1 = new Chromosome(InOutData.NumOfCity);
            Chromosome child2 = new Chromosome(InOutData.NumOfCity);
            nextPop.Clear();
            for (int i = 0; i < _populationSize; i += 1)
            {
                pidx1 = touranmentSelection(ran, curPop, touranmentSize);
                pidx2 = touranmentSelection(ran, curPop, touranmentSize);
                parent1 = ((Chromosome)curPop[pidx1]);
                parent2 = ((Chromosome)curPop[pidx2]);
                if ((float)(ran.NextDouble()) < _crossoverRate)
                {
                    parent1.linearDistanceCrossover2(parent2, out child1, ran, alpha1, alpha2, beta);
                    child1.inversionMutation(ran);
                    child1.calDistance = new Chromosome.CaculateDistance(InOutData.calculateDistance);
                    child1.calculateFitness(_maxCost);
                    nextPop.Add(child1);
                }
                else
                {
                    nextPop.Add(parent1);
                }
            }
            curPop.Clear();
            for (int i = 0; i < _populationSize; i++)
            {
                curPop.Add((Chromosome)nextPop[i]);
                if (((Chromosome)nextPop[i]).Fitness < ((Chromosome)nextPop[index]).Fitness)
                {
                    index = i;
                }
            }
            if (_elitism)
            {
                if (!compareTour(_bestChromosome, (Chromosome)curPop[index]))
                {
                    curPop.RemoveAt(0);
                    curPop.Add(_bestChromosome);
                }
            }
        }

        public void GA_LinearDistance1(float alpha1, float alpha2, float beta)
        {
            init();
            createRandomPopulation();
            _totalFitness = totalFitnessPopulation(presentPopulation);
            if (File.Exists(_fileName))
            {
                File.Delete(_fileName);
            }
            for (int i = 0; i < _generationSize; i++)
            {
                createNextPopulation_LinearDistance1(ref presentPopulation, nextPopulation, _touranmentSize, alpha1, alpha2, beta);
                _totalFitness = totalFitnessPopulation(presentPopulation);
                writeFitness(_fileName, presentPopulation, _totalFitness, i + 1, _bestChromosome);
            }
        }

        //GA use radius
        public void createNextPopulation_RadiusDistance(ref ArrayList curPop, ArrayList nextPop, int touranmentSize, int radius)
        {
            int index = 0;
            int pidx1, pidx2;
            Chromosome parent1 = new Chromosome(InOutData.NumOfCity);
            Chromosome parent2 = new Chromosome(InOutData.NumOfCity);
            Chromosome child1 = new Chromosome(InOutData.NumOfCity);
            Chromosome child2 = new Chromosome(InOutData.NumOfCity);
            nextPop.Clear();
            for (int i = 0; i < _populationSize; i += 1)
            {
                pidx1 = touranmentSelection(ran, curPop, touranmentSize);
                pidx2 = touranmentSelection(ran, curPop, touranmentSize);
                parent1 = ((Chromosome)curPop[pidx1]);
                parent2 = ((Chromosome)curPop[pidx2]);
                if ((float)(ran.NextDouble()) < _crossoverRate)
                {
                    parent1.MSCX_Radius(parent2, out child1, ran, radius);
                    child1.inversionMutation(ran);
                    child1.calDistance = new Chromosome.CaculateDistance(InOutData.calculateDistance);
                    child1.calculateFitness(_maxCost);
                    nextPop.Add(child1);
                }
                else
                {
                    nextPop.Add(parent1);
                }
            }
            curPop.Clear();
            for (int i = 0; i < _populationSize; i++)
            {
                curPop.Add((Chromosome)nextPop[i]);
                if (((Chromosome)nextPop[i]).Fitness < ((Chromosome)nextPop[index]).Fitness)
                {
                    index = i;
                }
            }
            if (_elitism)
            {
                if (!compareTour(_bestChromosome, (Chromosome)curPop[index]))
                {
                    curPop.RemoveAt(0);
                    curPop.Add(_bestChromosome);
                }
            }
        }

        public void GA_RadiusDistance(int radius)
        {
            init();
            createRandomPopulation();
            _totalFitness = totalFitnessPopulation(presentPopulation);
            if (File.Exists(_fileName))
            {
                File.Delete(_fileName);
            }
            for (int i = 0; i < _generationSize; i++)
            {
                createNextPopulation_RadiusDistance(ref presentPopulation, nextPopulation, _touranmentSize, radius);
                _totalFitness = totalFitnessPopulation(presentPopulation);
                writeFitness(_fileName, presentPopulation, _totalFitness, i + 1, _bestChromosome);
            }
        }

        //GA Hybridizing
        public void createNextPopulation_Hybridizing(ref ArrayList curPop, ArrayList nextPop, int touranmentSize)
        {
            int index = 0;
            int pidx1, pidx2;
            Chromosome parent1 = new Chromosome(InOutData.NumOfCity);
            Chromosome parent2 = new Chromosome(InOutData.NumOfCity);
            Chromosome child1 = new Chromosome(InOutData.NumOfCity);
            Chromosome child2 = new Chromosome(InOutData.NumOfCity);
            nextPop.Clear();
            for (int i = 0; i < _populationSize; i += 1)
            {
                pidx1 = touranmentSelection(ran, curPop, touranmentSize);
                pidx2 = touranmentSelection(ran, curPop, touranmentSize);
                parent1 = ((Chromosome)curPop[pidx1]);
                parent2 = ((Chromosome)curPop[pidx2]);
                if ((float)(ran.NextDouble()) < _crossoverRate)
                {
                    parent1.hybridizingCrossover(parent2, out child1, ran);
                    child1.inversionMutation(ran);
                    child1.calDistance = new Chromosome.CaculateDistance(InOutData.calculateDistance);
                    child1.calculateFitness(_maxCost);
                    nextPop.Add(child1);
                }
                else
                {
                    nextPop.Add(parent1);
                }
            }
            curPop.Clear();
            for (int i = 0; i < _populationSize; i++)
            {
                curPop.Add((Chromosome)nextPop[i]);
                if (((Chromosome)nextPop[i]).Fitness < ((Chromosome)nextPop[index]).Fitness)
                {
                    index = i;
                }
            }
            if (_elitism)
            {
                if (!compareTour(_bestChromosome, (Chromosome)curPop[index]))
                {
                    curPop.RemoveAt(0);
                    curPop.Add(_bestChromosome);
                }
            }
        }

        //crossover create two children
        public void createNextPopulation_Hybridizing1(ref ArrayList curPop, ArrayList nextPop, int touranmentSize)
        {
            int index = 0;
            int pidx1, pidx2;
            Chromosome parent1 = new Chromosome(InOutData.NumOfCity);
            Chromosome parent2 = new Chromosome(InOutData.NumOfCity);
            Chromosome child1 = new Chromosome(InOutData.NumOfCity);
            Chromosome child2 = new Chromosome(InOutData.NumOfCity);
            nextPop.Clear();
            for (int i = 0; i < _populationSize; i += 2)
            {
                pidx1 = touranmentSelection(ran, curPop, touranmentSize);
                pidx2 = touranmentSelection(ran, curPop, touranmentSize);
                parent1 = ((Chromosome)curPop[pidx1]);
                parent2 = ((Chromosome)curPop[pidx2]);
                if ((float)(ran.NextDouble()) < _crossoverRate)
                {
                    parent1.hybridizingCrossover1(parent2, out child1, out child2, ran);
                    child1.inversionMutation(ran);
                    child1.calDistance = new Chromosome.CaculateDistance(InOutData.calculateDistance);
                    child1.calculateFitness(_maxCost);
                    nextPop.Add(child1);
                    child2.inversionMutation(ran);
                    child2.calDistance = new Chromosome.CaculateDistance(InOutData.calculateDistance);
                    child2.calculateFitness(_maxCost);
                    nextPop.Add(child2);
                }
                else
                {
                    nextPop.Add(parent1);
                    nextPop.Add(parent2);
                }
            }
            curPop.Clear();
            for (int i = 0; i < _populationSize; i++)
            {
                curPop.Add((Chromosome)nextPop[i]);
                if (((Chromosome)nextPop[i]).Fitness < ((Chromosome)nextPop[index]).Fitness)
                {
                    index = i;
                }
            }
            if (_elitism)
            {
                if (!compareTour(_bestChromosome, (Chromosome)curPop[index]))
                {
                    curPop.RemoveAt(0);
                    curPop.Add(_bestChromosome);
                }
            }
        }

        public void GA_Hybridizing()
        {
            init();
            createRandomPopulation();
            _totalFitness = totalFitnessPopulation(presentPopulation);
            if (File.Exists(_fileName))
            {
                File.Delete(_fileName);
            }
            for (int i = 0; i < _generationSize; i++)
            {
                createNextPopulation_Hybridizing(ref presentPopulation, nextPopulation, _touranmentSize);
                _totalFitness = totalFitnessPopulation(presentPopulation);
                writeFitness(_fileName, presentPopulation, _totalFitness, i + 1, _bestChromosome);
            }
        }

        //crossover create two children
        public void GA_Hybridizing1()
        {
            init();
            createRandomPopulation();
            _totalFitness = totalFitnessPopulation(presentPopulation);
            if (File.Exists(_fileName))
            {
                File.Delete(_fileName);
            }
            for (int i = 0; i < _generationSize; i++)
            {
                createNextPopulation_Hybridizing1(ref presentPopulation, nextPopulation, _touranmentSize);
                _totalFitness = totalFitnessPopulation(presentPopulation);
                writeFitness(_fileName, presentPopulation, _totalFitness, i + 1, _bestChromosome);
            }
        }

        //GA_MSCX create two children
        public void createNextPopulationMSCX_TwoChildren(ref ArrayList curPop, ArrayList nextPop, int touranmentSize)
        {
            int index = 0;
            int pidx1, pidx2;
            Chromosome parent1 = new Chromosome(InOutData.NumOfCity);
            Chromosome parent2 = new Chromosome(InOutData.NumOfCity);
            Chromosome child1 = new Chromosome(InOutData.NumOfCity);
            Chromosome child2 = new Chromosome(InOutData.NumOfCity);
            nextPop.Clear();
            for (int i = 0; i < _populationSize; i += 2)
            {
                pidx1 = touranmentSelection(ran, curPop, touranmentSize);
                pidx2 = touranmentSelection(ran, curPop, touranmentSize);
                parent1 = ((Chromosome)curPop[pidx1]);
                parent2 = ((Chromosome)curPop[pidx2]);
                if ((float)(ran.NextDouble()) < _crossoverRate)
                {
                    //parent1.modifiedOrderCrossover(parent2, out child1, out child2, ran);
                    parent1.MSCX_TwoChildren(parent2, out child1, out child2, ran);
                    child1.inversionMutation(ran);
                    child2.inversionMutation(ran);                                    
                    child1.calDistance = new Chromosome.CaculateDistance(InOutData.calculateDistance);
                    child1.calculateFitness(_maxCost);
                    nextPop.Add(child1);
                    child2.calDistance = new Chromosome.CaculateDistance(InOutData.calculateDistance);
                    child2.calculateFitness(_maxCost);
                    nextPop.Add(child2);
                }
                else
                {
                    nextPop.Add(parent1);
                    nextPop.Add(parent2);
                }
            }
            curPop.Clear();
            for (int i = 0; i < _populationSize; i++)
            {
                curPop.Add((Chromosome)nextPop[i]);
                if (((Chromosome)nextPop[i]).Fitness < ((Chromosome)nextPop[index]).Fitness)
                {
                    index = i;
                }
            }
            if (_elitism)
            {
                if (!compareTour(_bestChromosome, (Chromosome)curPop[index]))
                {
                    curPop.RemoveAt(0);
                    curPop.Add(_bestChromosome);
                }
            }
        }
        public void GA_MSCX_TwoChildren()
        {
            init();
            createRandomPopulation();
            _totalFitness = totalFitnessPopulation(presentPopulation);
            if (File.Exists(_fileName))
            {
                File.Delete(_fileName);
            }
            for (int i = 0; i < _generationSize; i++)
            {
                createNextPopulationMSCX_TwoChildren(ref presentPopulation, nextPopulation, _touranmentSize);
                _totalFitness = totalFitnessPopulation(presentPopulation);
                writeFitness(_fileName, presentPopulation, _totalFitness, i + 1, _bestChromosome);
            }
        }

        //GA hybridizing PMX and MSCX
        public void createNextPopulationMSCX_PMX(ref ArrayList curPop, ArrayList nextPop, int touranmentSize)
        {
            int index = 0;
            int pidx1, pidx2;
            Chromosome parent1 = new Chromosome(InOutData.NumOfCity);
            Chromosome parent2 = new Chromosome(InOutData.NumOfCity);
            Chromosome child1 = new Chromosome(InOutData.NumOfCity);
            Chromosome child2 = new Chromosome(InOutData.NumOfCity);
            nextPop.Clear();
            for (int i = 0; i < _populationSize/2; i += 2)
            {
                pidx1 = touranmentSelection(ran, curPop, touranmentSize);
                pidx2 = touranmentSelection(ran, curPop, touranmentSize);
                parent1 = ((Chromosome)curPop[pidx1]);
                parent2 = ((Chromosome)curPop[pidx2]);
                if ((float)(ran.NextDouble()) < _crossoverRate)
                {
                    //parent1.modifiedOrderCrossover(parent2, out child1, out child2, ran);
                    parent1.PMX(parent2, out child1, out child2, ran);
                    child1.inversionMutation(ran);
                    child2.inversionMutation(ran);
                    child1.calDistance = new Chromosome.CaculateDistance(InOutData.calculateDistance);
                    child1.calculateFitness(_maxCost);
                    nextPop.Add(child1);
                    child2.calDistance = new Chromosome.CaculateDistance(InOutData.calculateDistance);
                    child2.calculateFitness(_maxCost);
                    nextPop.Add(child2);
                }
                else
                {
                    nextPop.Add(parent1);
                    nextPop.Add(parent2);
                }
            }
            for (int i = 0; i < _populationSize / 2; i += 1)
            {
                pidx1 = touranmentSelection(ran, curPop, touranmentSize);
                pidx2 = touranmentSelection(ran, curPop, touranmentSize);
                parent1 = ((Chromosome)curPop[pidx1]);
                parent2 = ((Chromosome)curPop[pidx2]);
                if ((float)(ran.NextDouble()) < _crossoverRate)
                {
                    //parent1.modifiedOrderCrossover(parent2, out child1, out child2, ran);
                    parent1.modifiedSequentialContructiveCrossover(parent2, out child1, ran);
                    child1.inversionMutation(ran);
                    //child2.inversionMutation(ran);
                    child1.calDistance = new Chromosome.CaculateDistance(InOutData.calculateDistance);
                    child1.calculateFitness(_maxCost);
                    nextPop.Add(child1);
                    //child2.calDistance = new Chromosome.CaculateDistance(InOutData.calculateDistance);
                    //child2.calculateFitness(_maxCost);
                    //nextPop.Add(child2);
                }
                else
                {
                    nextPop.Add(parent1);
                    //nextPop.Add(parent2);
                }
            }
            curPop.Clear();
            for (int i = 0; i < _populationSize; i++)
            {
                curPop.Add((Chromosome)nextPop[i]);
                if (((Chromosome)nextPop[i]).Fitness < ((Chromosome)nextPop[index]).Fitness)
                {
                    index = i;
                }
            }
            if (_elitism)
            {
                if (!compareTour(_bestChromosome, (Chromosome)curPop[index]))
                {
                    curPop.RemoveAt(0);
                    curPop.Add(_bestChromosome);
                }
            }
        }
        public void GA_MSCX_PMX()
        {
            init();
            createRandomPopulation();
            _totalFitness = totalFitnessPopulation(presentPopulation);
            if (File.Exists(_fileName))
            {
                File.Delete(_fileName);
            }
            for (int i = 0; i < _generationSize; i++)
            {
                createNextPopulationMSCX_PMX(ref presentPopulation, nextPopulation, _touranmentSize);
                _totalFitness = totalFitnessPopulation(presentPopulation);
                writeFitness(_fileName, presentPopulation, _totalFitness, i + 1, _bestChromosome);
            }
        }

        public void createNextPopulation_HybridizingMSCX7(ref ArrayList curPop, ArrayList nextPop, int touranmentSize, int[] indexArr)
        {
            int index = 0;
            int pidx1, pidx2;
            Chromosome parent1 = new Chromosome(InOutData.NumOfCity);
            Chromosome parent2 = new Chromosome(InOutData.NumOfCity);
            Chromosome parent3 = new Chromosome(InOutData.NumOfCity);
            Chromosome child1 = new Chromosome(InOutData.NumOfCity);
            Chromosome child2 = new Chromosome(InOutData.NumOfCity);
            nextPop.Clear();
            for (int i = 0; i < _populationSize / 2; i += 1)
            {
                pidx1 = touranmentSelection(ran, curPop, touranmentSize);
                pidx2 = touranmentSelection(ran, curPop, touranmentSize);
                parent1 = ((Chromosome)curPop[pidx1]);
                parent2 = ((Chromosome)curPop[pidx2]);
                if ((float)(ran.NextDouble()) < _crossoverRate)
                {
                    //parent1.modifiedOrderCrossover(parent2, out child1, out child2, ran);
                    parent1.M_MSCX6_1(parent2, parent3, out child1, ran);
                    child1.inversionMutation(ran);
                    //child2.inversionMutation(ran);
                    child1.calDistance = new Chromosome.CaculateDistance(InOutData.calculateDistance);
                    child1.calculateFitness(_maxCost);
                    nextPop.Add(child1);
                    //child2.calDistance = new Chromosome.CaculateDistance(InOutData.calculateDistance);
                    //child2.calculateFitness(_maxCost);
                    //nextPop.Add(child2);
                }
                else
                {
                    nextPop.Add(parent1);
                    //nextPop.Add(parent2);
                }
            }
            for (int i = 0; i < _populationSize / 2; i += 1)
            {
                pidx1 = touranmentSelection(ran, curPop, touranmentSize);
                pidx2 = touranmentSelection(ran, curPop, touranmentSize);
                parent1 = ((Chromosome)curPop[pidx1]);
                parent2 = ((Chromosome)curPop[pidx2]);
                if ((float)(ran.NextDouble()) < _crossoverRate)
                {
                    //parent1.modifiedOrderCrossover(parent2, out child1, out child2, ran);
                    parent1.modifiedSequentialContructiveCrossover(parent2, out child1, ran);
                    child1.inversionMutation(ran);
                    //child2.inversionMutation(ran);
                    child1.calDistance = new Chromosome.CaculateDistance(InOutData.calculateDistance);
                    child1.calculateFitness(_maxCost);
                    nextPop.Add(child1);
                    //child2.calDistance = new Chromosome.CaculateDistance(InOutData.calculateDistance);
                    //child2.calculateFitness(_maxCost);
                    //nextPop.Add(child2);
                }
                else
                {
                    nextPop.Add(parent1);
                    //nextPop.Add(parent2);
                }
            }
            curPop.Clear();
            for (int i = 0; i < _populationSize; i++)
            {
                curPop.Add((Chromosome)nextPop[i]);
                if (((Chromosome)nextPop[i]).Fitness < ((Chromosome)nextPop[index]).Fitness)
                {
                    index = i;
                }
            }
            if (_elitism)
            {
                if (!compareTour(_bestChromosome, (Chromosome)curPop[index]))
                {
                    curPop.RemoveAt(0);
                    curPop.Add(_bestChromosome);
                }
            }
        }
        public void GA_HyBridizing_MSCX7()
        {
            init();
            createRandomPopulation();
            _totalFitness = totalFitnessPopulation(presentPopulation);
            if (File.Exists(_fileName))
            {
                File.Delete(_fileName);
            }
            int[] indexArr = new int[InOutData.NumOfCity];
            indexArr = sortCities(InOutData.cities, InOutData.NumOfCity);
            for (int i = 0; i < _generationSize; i++)
            {
                createNextPopulation_HybridizingMSCX7(ref presentPopulation, nextPopulation, _touranmentSize, indexArr);
                _totalFitness = totalFitnessPopulation(presentPopulation);
                writeFitness(_fileName, presentPopulation, _totalFitness, i + 1, _bestChromosome);
            }
        }

    }
}
